//
// Created by LiuYou on 2021/12/6.
//

#include <iostream>
#include <vector>
#include <random>
#include <iterator>
#include <algorithm>


namespace Sort {

    static int random(int left, int right) {
        std::random_device randomDevice;
        std::default_random_engine randomEngine( randomDevice());
        std::uniform_int_distribution<> uniformIntDistribution( left, right );
        return uniformIntDistribution( randomEngine );
    }

}


int main(int argc, char** argv) {
    {
        std::vector<int> arr;
        arr.reserve( 10 );
        for (int i = 0; i < 10; ++i) {
            arr.emplace_back( Sort::random( 0, 100 ));
        }

        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << std::endl;

        std::cout << "pivot = " << arr[arr.size() - 1] << std::endl;

        std::stable_partition( arr.begin(), arr.end(), [&](const auto& item) {
            return item < arr[arr.size() - 1];
        } );

        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << std::endl;
    }


    std::cout << "=====================================================================" << std::endl;
    {
        std::vector<double> arr{65, 75, 56, 48, 31, 28, 32, 44, 40, 41, 44, 50};
        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << std::endl;
        // todo 笔记: partition();和stable_partition();返回的是分区序列中第一个分区的结束迭代器。
        auto iter = std::stable_partition( arr.begin(), arr.end(), [&](const auto& item) {
            return item <= 44;

//            if (item <= 44) {
//                return true;
//            } else {
//                return false;
//            }
        } );

        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << std::endl;
        std::cout << *iter << std::endl;

        bool isPartitioned = std::is_partitioned( arr.begin(), arr.end(), [&](const auto& item) {
            return item <= 44;
        } );
        std::cout << std::boolalpha << isPartitioned << std::endl;

        // todo 笔记: partition_point();返回的也是分区序列中第一个分区的结束迭代器。
        const auto& iterator =
                std::partition_point( arr.begin(), arr.end(),
                                      [&](const auto& item) {
                                          return item <= 44;
                                      } );
        std::cout << *iterator << std::endl;
    }


    return 0;
}
